﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class CoinChange
    {
        public CoinChange()
        {
            int testCase = Int32.Parse(TestConsole.ReadLine());
            while (testCase-- > 0)
            {
                string[] input = TestConsole.ReadLine().Split(' ');
                int money = Int32.Parse(input[0]);
                int typeCount = Int32.Parse(input[1]);
                int[] type = new int[typeCount];
                input = TestConsole.ReadLine().Split(' ');
                for (int i = 0; i < typeCount; i++)
                {
                    type[i] = Int32.Parse(input[i]);
                }
                int gcd = GCD(type);
                int[,] board = new int[type.Length, money / gcd + 1];
                for (int i = 0; i < type.Length; i++)
                {
                    int turm = type[i] / gcd;
                    for (int j = 0; j * gcd <= money; j++)
                    {
                        if (i == 0)
                        {
                            board[i, j] = (j * gcd % type[i] == 0) ? 1 : 0;
                        }
                        else
                        {
                            if (j * gcd < type[i])
                            {
                                board[i, j] = board[i - 1, j];
                            }
                            else
                            {
                                board[i, j] = board[i - 1, j] + board[i, j - turm];
                                if (board[i, j] > 1000000007)
                                {
                                    board[i, j] = board[i, j] - 1000000007;
                                }
                            }
                        }
                    }
                }
                Console.WriteLine(board[type.Length - 1, money / gcd]);
            }
        }
        private int GCD(int[] number)
        {
            int a = number[0];
            for (int i = 1; i < number.Length; i++)
            {
                a = GCD(a, number[i]);
            }
            return a;
        }
        private int GCD(int a, int b)
        {
            int tmp = 0;
            if (a < b)
            {
                tmp = a;
                a = b;
                b = tmp;
            }
            a = a % b;
            while (a > 0)
            {
                tmp = a;
                a = a % b;
                b = tmp;                
            }
            return b;
        }
    }
}
